package binary_tree.LeetCode;

/**
 * 将二叉搜索树转换为双向链表
 */
public class JZ36 {

    /**
     * 传入一个二叉搜索树的根节点，就可以将其转换为排序后的双向链表，返回链表的头节点
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null){
            return null;
        }
        //先将左子树转换为排序后的双向链表
        TreeNode lefthead=Convert(pRootOfTree.left);
        //找到lefthead的尾节点
        TreeNode lefttail=lefthead;
        while (lefttail!=null&&lefttail.right!=null){
            lefttail=lefttail.right;
        }
        //连接根节点，当左子树为空时就不需要拼接，所以进行判空处理
        if (lefttail!=null){
            pRootOfTree.left=lefttail;
            lefttail.right=pRootOfTree;
        }
        //将右子树转换为排序后的双向链表
        TreeNode righhead=Convert(pRootOfTree.right);
        //将rightnode和根节点拼接,当右子树为空时不需要拼接，所以判空处理
        if (righhead!=null){
            righhead.left=pRootOfTree;
            pRootOfTree.right=righhead;
        }
        //返回时注意lefthead是否为空
        return lefthead==null?pRootOfTree:lefthead;
    }
}
